package leetcode.code0957;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

/**
 * 暴力超时
 * @author CaoYu
 * @date 2021年9月30日
 * @description
 */
public class Solution957_1 implements IDebug {

	private class Pos {
		public int index;
		public Integer odd2;// 奇数去
		public Integer even2;// 偶数去

		public Pos(int index, Integer odd2, Integer even2) {
			super();
			this.index = index;
			this.odd2 = odd2;
			this.even2 = even2;
		}

	}

	public int oddEvenJumps(int[] arr) {
		int len = arr.length;
		Pos[] poses = new Pos[len];
		int to = len - 1;
		for (int i = 0; i < to; i++) {
			int vali = arr[i];
			int min = Integer.MAX_VALUE;
			int max = Integer.MIN_VALUE;
			Integer odd2 = null;// 奇数去
			Integer even2 = null;// 偶数去
			for (int j = i + 1; j < len; j++) {
				int valj = arr[j];
				if (valj == vali) {
					min = valj;
					max = valj;
					odd2 = j;
					even2 = j;
					break;
				} else if (valj > vali && valj < min) {
					min = valj;
					odd2 = j;
				} else if (valj < vali && valj > max) {
					max = valj;
					even2 = j;
				}
			}
			poses[i] = new Pos(i, odd2, even2);
		}
		poses[to] = new Pos(to, null, null);
		int ans = 1;
		Boolean[][] dp = new Boolean[len][2];// 0 odd ? 1 even?
		for (int i = to - 1; i >= 0; i--) {
			Pos pos = poses[i];
			boolean odd = true;
			while (true) {
				if (odd) {
					if (dp[pos.index][0] != null) {
						dp[i][0] = dp[pos.index][0];
						if (dp[i][0]) {
							ans++;
						}
						break;
					}
					if (pos.odd2 == null) {
						dp[pos.index][0] = false;
						dp[i][0] = false;
						break;
					} else {
						pos = poses[pos.odd2];
					}
				} else {
					if (dp[pos.index][1] != null) {
						dp[i][0] = dp[pos.index][1];
						if (dp[i][0]) {
							ans++;
						}
						break;
					}
					if (pos.even2 == null) {
						dp[pos.index][1] = false;
						dp[i][0] = false;
						break;
					} else {
						pos = poses[pos.even2];
					}
				}
				if (pos.index == to) {
					ans++;
					dp[i][0] = true;
					if (odd) {
						dp[pos.index][0] = true;
					} else {
						dp[pos.index][1] = true;
					}
					break;
				}
				odd = !odd;
			}
		}
		return ans;
	}

	@Override
	public void debug1() {
		String str = "[10,13,12,14,15]";
		int e = 2;
		int r = this.oddEvenJumps(HelpDebug.str2array3(str));
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug2() {
		String str = "[2,3,1,1,4]";
		int e = 3;
		int r = this.oddEvenJumps(HelpDebug.str2array3(str));
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug3() {
		String str = "[5,1,3,4,2]";
		int e = 3;
		int r = this.oddEvenJumps(HelpDebug.str2array3(str));
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug4() {
		String str = "[1,2,3,2,1,4,4,5]";
		int e = 6;
		int r = this.oddEvenJumps(HelpDebug.str2array3(str));
		HelpDebug.compare(e, r);
	}
	//[31,28,8,41,20,28,41,26,46,30,
	// 41,34,2,29,24,39,28,11,22,21,
	// 33,15,14,35,49,23,
	// 15,46,19,28,13,19,38]//index 26 -> 28 -> 31 -> 32
	public void debug5() {
		String str = "[31,28,8,41,20,28,41,26,46,30,41,34,2,29,24,39,28,11,22,21,33,15,14,35,49,23,15,46,19,28,13,19,38]";
		int e = 21;
		int r = this.oddEvenJumps(HelpDebug.str2array3(str));
		HelpDebug.compare(e, r);
	}

	public static void main(String[] args) {
		Solution957_1 so = new Solution957_1();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
	}

}
